#include<stdio.h>
#include<stdlib.h>



struct base
{
int data;
struct base *next;
} *first=NULL, *last=NULL;



void primary_menu();
void newlinkedlist();
void appendlist(int );
void extendlist();
void insertlist(int , int );
void removeitem(int );
void popitem();
void countitem(int );
void sortlist();
void reverselist();
void indexitem(int );
void display();



void primary_menu()
{
int ch1=1, ch2;
printf("\n\nThis program demostrates python's list operations");
printf("\nin C using linked lists");
while(ch1==1)
{
printf("\n\nPROGRAM MENU");
printf("\n\n1. Input new list");
printf("\n2. Display list");
printf("\n3. Append");
printf("\n4. Extend");
printf("\n5. Insert");
printf("\n6. Remove");
printf("\n7. Pop");
printf("\n8. Count");
printf("\n9. Sort");
printf("\n10. Reverse");
printf("\n11. Index");
printf("\n12. Exit");
printf("\nInput choice : ");
scanf("%d", &ch2);
switch(ch2)
{
case 1 : newlinkedlist();
	 break;
case 2 : display();
	 break;
case 3 : printf("\nInput value to append at end : ");
	 int val;
	 scanf("%d", &val);
	 appendlist(val);
	 display();
	 break;
case 4 : extendlist();
	 display();
	 break;
case 5 : printf("\nInput value to insert : ");
	 int inval, pos;
	 scanf("%d", &inval);
	 printf("\nPosition to insert : ");
	 scanf("%d", &pos);
	 insertlist(inval, pos);
	 break;
case 6 : printf("\nEnter element to remove from list : ");
	 int rmval;
	 scanf("%d", &rmval);
	 removeitem(rmval);
	 break;
case 7 : popitem();
	 break;
case 8 : printf("\nEnter value for which occurences have to be found : ");
	 int oval;
	 scanf("%d", &oval);
	 countitem(oval);
	 break;
case 9 : sortlist();
	 break;
case 10 : reverselist();
	  break;
case 11 : printf("\nEnter element whose index is to be found : ");
	  int indval;
	  scanf("%d", &indval);
	  indexitem(indval);
	  break;
case 12 : ch1=0;
	  break;
default : printf("\n\nWrong input value!!!\n");
	  break;
}
}
}



void newlinkedlist()
{
int num,flag=0;
int ch=1;
struct base *node;
printf("\n");
while(ch==1)
{
if(flag==0)
{
printf("\nEnter the element : ");
scanf("%d", &num);
node = malloc(sizeof(struct base));
node->data=num;
node->next=NULL;
first=node;
last=node;
flag=1;
display();
}
else
{
printf("\nEnter the element : ");
scanf("%d", &num);
node = malloc(sizeof(struct base));
node->data=num;
node->next=NULL;
last->next=node;
last=node;
display();
}
printf("\nInput 1 to enter more elements");
printf("\nChoice : ");
scanf("%d", &ch);
}
}



void appendlist(int num)
{
struct base *node;
node=malloc(sizeof(struct base));
node->data=num;
node->next=NULL;
if(first==NULL)
{
first=node;
last=first;
}
else
{
last->next=node;
last=node;
}
}



void extendlist()
{
int num;
printf("\n\nInput number of nodes to extend into list : ");
scanf("%d", &num);
int a[num];
int i;
for(i=0;i<num;i++)
{
printf("\nInput value %d : ", i+1);
scanf("%d", &a[i]);
appendlist(a[i]);
}
}



void insertlist(int num, int pos)
{
int cnt=1, flag=0;
struct base *item, *node;
node=malloc(sizeof(struct base));
item=first;
while(item!=NULL)
{
if(pos==1)
{
node->data=num;
node->next=first;
first=node;
flag=1;
display();
break;
}
else if(pos==cnt+1)
{
node->data=num;
node->next=item->next;
item->next=node;
display();
flag=1;
break;
}
else
cnt++;
item=item->next;
}
if(flag==0)
printf("\nThe position specified does not exist in the list\n");
}



void removeitem(int num)
{
struct base *temp;
temp=first;
while(temp!=NULL)
{
if(temp!=last)
{
if((temp->next!=last) && (temp->next->data==num))
{
temp->next=temp->next->next;
break;
}
else if((temp->next->data==num) && (temp->next==last))
{
temp->next=temp->next->next;
last=temp;
break;
}
}
if(temp==first)
{
if(first->data==num)
{
first=temp->next;
break;
}
}
temp=temp->next;
}
display();
}



void popitem()
{
struct base *node;
node=first;
while(node!=NULL)
{
if(node->next==last)
{
node->next=NULL;
last=node;
printf("\nItem popped!!");
break;
}
if(first==last)
{
first=NULL;
last=NULL;
printf("\nItem popped!!");
break;
}
node=node->next;
}
display();
}



void countitem(int num)
{
int occ=0;
struct base *node;
node=first;
while(node!=NULL)
{
if(node->data==num)
occ++;
node=node->next;
}
if(occ!=0)
{
display();
printf("\nThe number of occurences of %d are : %d\n", num, occ);
}
else
printf("\n%d is not present in the list...\n", num);
}



void sortlist()
{
struct base *t1,*t2;
int storage;
t1=first;
while(t1->next!=NULL)
{
t2=t1->next;
while(t2!=NULL)
{
if((t2->data)<(t1->data))
{
storage=t1->data;
t1->data=t2->data;
t2->data=storage;
}
t2=t2->next;
}
t1=t1->next;
}
printf("\nList successfully sorted!!");
display();
}



void reverselist()
{
struct base *temp1,*temp2,*temp3;
temp1 = first;
temp2 = NULL;
temp3 = NULL;
while(temp1!=NULL)
{
first=temp1;
if(temp3==NULL)
{
temp2=temp1->next;
temp1->next=temp3;
temp3=temp1;
temp1=temp2;
last=temp3;
}
else
{
temp2=temp1->next;
temp1->next=temp3;
temp3=temp1;
temp1=temp2;
}
}
printf("\nSuccessfully reversed list");
display();
}



void indexitem(int num)
{
int position=1;
struct base *temp=first;
while(temp!=NULL)
{
if(temp->data==num)
{
printf("\nElement found at position %d\n", position);
break;
}
position++;
temp=temp->next;
}
}



void display()
{
struct base *t;
if(first!=NULL)
{
printf("\n\nThe List is : ");
t=first;
while(t!=NULL)
{
if(t->next!=NULL)
printf("%d ",t->data);
else
printf("%d", t->data);
t=t->next;
}
printf("\n");
}
else
printf("\nThe list is empty\n");
}



void main()
{
primary_menu();
printf("\n");
}
